#include "DynamicArray.h"
#include <stdio.h>
#include <stdlib.h>

//动态数组
struct DynamicArray
{
    ElementType *array; //数组指针
    int capacity;   //数组容量（整个数组所占的空间大小）
    int size;       //数组大小
    void (*FreePtr)(ElementType);    //释放函数的函数指针
};

DArray *InitDArray(int capacity, void (*FreePtr)(ElementType))
{
    DArray *a = (DArray*)malloc(sizeof(DArray));
    if(a == NULL)
    {
        printf("申请DArray失败!\n");
        return NULL;
    }

    //初始化结构体变量
    a->FreePtr = FreePtr;
    a->capacity = capacity;
    a->size = 0;
    a->array = (ElementType*)malloc(sizeof(ElementType) * a->capacity);
    if(a->array == NULL)
    {
        printf("申请数组失败！\n");
        free(a);    //数组申请失败把结构体一起释放掉
        return NULL;
    }

    return a;
}

void FreeDArray(void *ptr)
{
    DArray *a = (DArray*)ptr;
    //结构体变量不为空
    if(a)
    {
        //数组指针不为空
        if(a->array)
        {
            //释放的函数指针不为空
            if(a->FreePtr != NULL)
            {
                //释放数组中存储的指针指向的内存
                for(int i = 0; i < a->size; i++)
                {
                    a->FreePtr(a->array[i]);
                }
            }
            free(a->array);
        }
    free(a);
    }  
}

bool InsertTail(DArray *a, ElementType element)
{
    //数组放满了
    if(a->size >= a->capacity)
    {
    #if 0
        ElementType *newP = (ElementType*)malloc(sizeof(ElementType) * a->capacity * 2);
        if(newP == NULL)
        {
            printf("申请空间失败!\n");
            return false;
        }
        for(int i = 0; i < a->size; i++)
        {
            newP[i] = a->array[i];
        }
        free(a->array);
        a->array = newP;
        a->capacity *= 2;
    #endif
        
    #if 1
        ElementType *newp = (ElementType*)realloc(a->array, sizeof(ElementType) * a->capacity * 2);
        if(newp == NULL)
        {
            printf("申请空间失败!\n");
            return false;
        }
        a->capacity *= 2;
        a->array = newp;
    #endif
    }
    a->array[a->size++] = element;
    return true;
}

ElementType FindByElement(DArray *a, ElementType element, bool (*find)(ElementType, ElementType))
{
    for(int i = 0; i < a->size; i++)
    {
        if(find(a->array[i], element) == true)
        {
            return a->array[i];
        }
    }
    return NULL;
}

void RemoveByIndex(DArray *a, int index)
{
    if(index < 0 || index >= a->size)
    {
        printf("非法的删除位置!\n");
        return;
    }

    if(a->FreePtr != NULL)
    {
        //释放要删除的位置的指针
        a->FreePtr(a->array[index]);
    }

    for(int i = index; i < a->size - 1; i++)
    {
        a->array[i] = a->array[i+1];
    }
    a->size--;
}

void RemoveByElement(DArray *a, ElementType element)
{
    for(int i = 0; i < a->size; i++)
    {
        if(a->array[i] == element)
        {
            RemoveByIndex(a, i);
            i--;
        }
    }
}

void PrintArray(DArray *a, void (*print)(ElementType))
{
    // printf("size = %d capacity = %d\n", a->size, a->capacity);
    for(int i = 0; i < a->size; i++)
    {
        print(a->array[i]);
    }
    printf("\n");
}

void FastSort(ElementType *a, int start, int end, bool (*SortPtr)(ElementType, ElementType))
{
    // 终止条件
    if(start >= end)
        return;

    int left = start;
    int right = end;
    ElementType temp = a[left];

    while(left < right)
    {
        // 先从右边动 找比基准值小的数
        while(SortPtr(a[right], temp) == true && left < right)
            right--;
        // 把右边的值赋给左边的空位 
        if(left < right)
            a[left] = a[right];
        // 左边动 找比基准值大的数
        while(SortPtr(temp, a[left]) == true && left < right)
            left++;
        // 把左边的值赋给右边的空位
        if(left < right)
            a[right--] = a[left];
    }
    // 基准值给到这个位置
    a[left] = temp;

    // 递归排序
    FastSort(a, start, left - 1, SortPtr);
    FastSort(a, right + 1, end, SortPtr);
}

void DArrayFastSort(DArray *a, bool (*SortPtr)(ElementType, ElementType))
{
    FastSort(a->array, 0, a->size - 1, SortPtr);
}

ElementType BinarySearch(DArray *a, ElementType element, int (*BSearch)(ElementType, ElementType))
{
    int left = 0;
    int right = a->size - 1;
    while(left <= right)
    {
        // int mid = left + (right - left) / 2;
        int mid = (left & right) + ((left ^ right) >> 1);   // 要把后面异或求平均值的部分整个括起来！
        // 比中间值小
        if(BSearch(a->array[mid], element) > 0)
            // 左半边找
            right = mid - 1;
        else if(BSearch(a->array[mid], element) < 0)
            // 右半边找
            left = mid + 1;
        else
            // 找着了
            return a->array[mid];
    }
    // 没找到
    return NULL;
}
